package ppd;

import java.util.HashMap;
import java.util.Map;

/**
 * LRU缓存
 */
public class LRUTest {


    public static void main(String[] args) {

        LRUCache lruCache = new LRUCache(2);
        lruCache.put(1, 1);
        lruCache.put(2, 2);
        System.out.println(lruCache.get(1));
        lruCache.put(3, 3);
        System.out.println(lruCache.get(2));
        lruCache.put(4, 4);
        System.out.println(lruCache.get(1));
        System.out.println(lruCache.get(3));
        System.out.println(lruCache.get(4));
    }

    /**
     * 缓存类
     */
    public static class LRUCache {

        static class Node{
            int key;

            int value;

            Node pre;

            Node next;

            public Node(int key, int value){
                this.key = key;
                this.value = value;
            }

        }

        /**
         * LRU容量
         */
        private int size;
        private Map<Integer, Node> map;
        private Node head;
        private Node tail;

        public LRUCache(int size){
            this.size = size;
            this.map = new HashMap<>(size);
            this.head = new Node(0, 0);
            this.tail = new Node(0, 0);
            head.next = tail;
            tail.pre = head;
        }

        int get(int key){
            if(map.containsKey(key)){
                Node node = map.get(key);
                remove(node);
                moveHead(node);
                return node.value;
            }
            return -1;
        }

        void put(int key, int value){
            if(map.containsKey(key)){
                Node node = map.get(key);
                node.value = value;
                remove(node);
                moveHead(node);
            }else{
                Node node = new Node(key, value);
                if(map.size() >= size){
                    map.remove(tail.pre.key);
                    remove(tail.pre);
                }
                map.put(key, node);
                moveHead(node);
            }
        }

        void remove(Node node){
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }

        void moveHead(Node node){
            node.pre = head;
            node.next = head.next;
            head.next.pre = node;
            head.next = node;
        }




    }
}
